1. Field of the Invention
The present invention relates to an information recording and reproducing apparatus for recording/reproducing information on a disk-shaped information recording medium block by block. In particular, the present invention relates to an information recording and reproducing apparatus having both history caching and read-ahead caching functions.
2. Description of the Related Art
In recent years, the operation speed of host computers has increased, making a large gap between the computer speed and the speed of external storage apparatuses (e.g., information recording and reproducing apparatus such as hard disk drives and optical disk drives). In order to reduce this gap, the speed of external storage apparatuses has been increased. There are two general methods for achieving improvement in the speed of an external storage apparatus: One is a physical improvement in speed, which is achieved by enhancing the rotation rate of a storage medium and reducing the seek time, i.e., the time required for a head to move to a target track of a storage medium. The other is a logical improvement, which is achieved by data caching techniques, that is, incorporating a buffer composed of a semiconductor memory in the apparatus and transferring data which is requested by a host computer and happens to be in the buffer to the host computer, without accessing the recording medium.
Data cache is classified into read caching and write caching. Read caching increases the speed of reproduction operations, whereas write caching increases the speed of recording operations. Read caching is further classified into a history type and a read-ahead type. According to history read caching, data which has previously been requested by a host computer is retained as cache data. According to read-ahead read caching, data which is next to data requested by a host computer is retained as cache data in advance.
In the field of large-scale computers, history read caching has long been studied with an aim to construct a hierarchial structure having components ranging from high-speed and low-capacity memories to low-speed and high-capacity memories into a high-speed and high-capacity memory as a whole.
According to the history read caching technique, a high-speed memory is divided into a plurality of smaller regions (referred to as "pages") so as to retain and manage data which has previously been read from a low-speed memory. If requested data happens to be in one of the pages (described as a "hit"), the data in that page is transferred as required data instead of reading from the low-speed memory. If the requested data is not in any pages of the high-speed memory (described as a "mis-hit"), data is read from the low-speed memory into a page so as to be transferred as the requested data. If every page of the high-speed memory stores previously requested data, it is necessary to discard the old data stored in one of the pages in order to read data from the low-speed memory into that page. The algorithms for history read caching can be classified according to the method of selecting the page of which data should be discarded. One popular algorithm for history read caching is a LRU (Least Recently Use) algorithm (An application of the LRU algorithm to a magnetic bubble memory is described in U.S. Pat. No. 3,737,881 issued to Vincent A. Cordi et al). According to the LRU algorithm, when there has been a mis-hit, the data in the page for which has not been accessed for the longest time is discarded so as to store information from a high-speed memory in that page. This algorithm utilizes the fact that the more recently the data has been accessed, the more likely the data is to be referred to again.
Read-ahead type read caching will now be described. According to this technique, the reproduction speed of an information recording and reproducing apparatus for recording/reproducing information on a disk-shaped information recording medium, e.g., a hard disk drive, is enhanced by eliminating moments during which the device is required to wait for the rotation of the disk. Usually, when an OS (Operation System) or an application which works on a computer tries to read out a file, it does not request the entire file to be reproduced at a time, but sequentially requests smaller units of the file, beginning from the top of the file. Such accesses are referred to as sequential accesses. For example, a case is contemplated where sequential accesses are made to blocks 1 to 10 in a block-by-block manner. This case will be described with reference to FIG. 19, which is a conceptual diagram showing a disk-shaped information recording medium.
In FIG. 19, each small fan-shaped portion represents a "sector", the number written in each sector representing the sector number thereof. A concentric group of sectors constitute a track. Reference numerals T0 to T2 represent the track numbers of the respective tracks. In the case where sectors are disposed in a spiral arrangement, one cycle of the spiral defines a track. For conciseness, sector s of track t will be referred to as (t, s) hereinafter. Block 1 corresponds to (T0, 1). Block 2 corresponds to (T0, 2) . . . Block 10 corresponds to (T0, 10). If the information recording medium rotates counterclockwise, the blocks in one concentric circle (track) are accessed clockwise.
When a host computer requests block 1, the information recording and reproducing apparatus accesses (T0, 1) by using a head and transfers the data reproduced therefrom to the host computer. Even if the host computer requests block 2 immediately afterward, the head is passing by (T0, 2). Accordingly, the head must wait until the information recording medium makes an almost complete turn (i.e., rotate once) before the head can access (T0, 2). In other words, one rotation is required in order to reproduce information stored in one block. As a result, 10 rotations are required in order to reproduce information stored in blocks 1 to 10. In order to solve this problem, when a host computer requests the reproduction of information in a given block, blocks that are located forward with respect to the one that is requested by the host computer are read in a high-speed memory (i.e., a data buffer composed of a semiconductor memory). If a block which is requested next has been read into the data buffer (described as a "hit") in advance, the data in the data buffer is transferred to the host computer without accessing the information recording medium. According to this technique, it is possible to reproduce the data stored in blocks 1 to 10 by only one rotation of the information recording medium. Recently, Iida et al. has disclosed an information recording and reproducing apparatus in Japanese Laid-Open Patent Publication No. 5-274090, which information recording and reproducing apparatus features read-ahead type read caching. Since a large number of consecutive blocks are read out in sequential accesses, it is often the case that the data buffer is used as a ring buffer (i.e., when the last end of the buffer is reached, the control returns to the top end of the buffer).
In order to obtain an information recording and reproducing apparatus capable of both history type read caching and read-ahead type read caching based on a conventional technique, the following scheme is required:
(1) an internal data buffer is split into two, one being defined as a history cache data region and the other being defined as a read-ahead cache data region; PA1 (2) a history type algorithm is applied to the history cache data region, while a read-ahead type algorithm is applied to the read-ahead cache data region; PA1 (3) on receiving a request from a host computer, a retrieval is attempted to determine which cache data a requested block hits; PA1 (4) if the requested block does not "hit" at (3), the block is read out from the information recording medium to the internal data buffer; and (5) it is determined which algorithm should be applied to the block that was read out at (4), which is to be stored as cache data. PA1 (Step U1) Seek a target track; PA1 (Step U2) Rotation waiting (by 1/2 rotations on average) till the head arrives at the target sector; PA1 (Step U3) Erase one sector (i.e., target sector); PA1 (Step U4) Rotation waiting (by 1 rotation) till the head arrives at the target sector; PA1 (Step U5) Record one sector (i.e., target sector); PA1 (Step U6) Rotation waiting (by 1 rotation) till the head arrives at the target sector; and PA1 (Step U7) One sector (i.e., target sector) is reproduced for verification.
However, the history type algorithm and the readahead type algorithm are completely different from each other, so that it is difficult to dynamically vary the sizes of the respective cache data regions. Accordingly, the internal buffer is likely to be split into the two regions at a fixed boundary at (1).
Next, write caching will be described. Representative write caching techniques are write-through caching and write-back caching. One similarity between the two write caching techniques is that when the content of a low-speed memory is updated, the change is reflected on a high-speed memory, so that the high-speed memory is accessed when referring to the updated content of the low-speed memory. The method for managing the data in the high-speed memory is similar to that of history type read caching. The two write caching techniques are different in that, according to the write-through caching, the control must wait until the low-speed memory is updated, whereas according to the write-back caching, the control does not wait until the low-speed memory is updated. Although both techniques can reduce the amount of time required for referring to information, only the write-back caching can reduce the amount of time required for updating information.
When a recording operation for one sector is required, an information recording and reproducing apparatus in which an disk-shaped information recording medium is rotated, e.g., a hard disk drive or an optical disk drive, requires a seek time (during which a head moves to a track including a target sector) and a rotation waiting time (during which the target sector is reached). In particular, an optical disk drive requires extra time because the content of the sector is erased before the recording, and a verification reproduction is performed after the recording. FIG. 20 shows a recording operation of an optical disk drive. The operation is as follows:
Thus, a sum of an average rotation waiting time of 2.5 rotations plus seek time is required for performing a recording for one sector. This is very slow compared with the speed of the bus to which a host computer and the optical disk drive are connected. Accordingly, by adopting the write-back caching technique, under which the host computer is notified that a recording operation is complete as soon as data to be recorded is stored in a data buffer in the optical disk drive, followed bv the actual recording of the data stored in the data buffer on the optical disk, the speed of the recording operation as viewed from the host computer is improved. In the case of a hard disk drive, recording data in one sector requires a sum of an average rotation waiting time of 0.5 rotations plus seek time. However, this is also slow compared with the speed of the bus to which a host computer and the hard disk drive are connected, so that the adoption of write-back caching can increase the speed of recording operations as viewed from the host computer.
As described earlier, history type read caching utilizes the fact that the more recently a block has been referred to, the more likely the block is to be referred to again. Read-ahead type read caching utilizes the fact that blocks lying ahead of a block that has been referred to are likely to be referred to. Since these two types of read caching are based on different facts, it is difficult to realize both types of read caching. Even if both types of read caching are achieved, there is a problem in that one type of read caching may hinder the performance of the other.
Moreover, if a recording is requested from a host computer while reproducing read-ahead cache data from the information recording medium, the recording operation must wait until the completion of the reproduction of the read-ahead cache data, since the data to be recorded is to be treated as history cache data, which cannot be managed in common with read-ahead cache data.
There is also a problem in that, when a reproduction is requested from a host computer while recording is performed on the information recording medium by the write-back caching technique, the reading of the reauested data, even if present in the cache data, must wait until the completion of the recording on the information recording medium.
There is also a problem in that, although the write-back caching technique improves the speed of the recording operation as viewed from the host computer, the amount of time required for the actual recording on the information recording medium is not reduced.